\documentclass[a4paper, 12pt, titlepage]{article}
\usepackage[cm]{fullpage}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{times}
\usepackage{cite}
\usepackage{xcolor}
\usepackage[pdftex]{graphicx}
\usepackage{indentfirst}
\usepackage{amsfonts}
\usepackage{longtable}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{amsmath}
\newtheorem{ru_def}{Определение}
\usepackage[pdftex, unicode]{hyperref}
 \hypersetup{
    pdfnewwindow=true,      % links in new window
    colorlinks=true,        % false: boxed links; true: colored links
    linkcolor=black,        % color of internal links
    urlcolor=blue,          % color of external links
    citecolor=black
}

%\usepackage[margin=10pt,font=small,labelfont=bf]{caption}
\usepackage{caption2}
\renewcommand{\captionlabeldelim }{.}

%\renewcommand{\thesection}{\arabic{section}.}

\graphicspath{{pics/}}

\clubpenalty=10000
\widowpenalty=10000

\begin{document}
\sloppy
\section*{Результаты работы арифметического нумерационного кодирования}
%Результаты вычислений по шагам выполнения задания.

Кодируемая последовательность:

<<Не узнавай друга в три дня, узнавай в три года>>\\

Последовательность, сфомированная кодером ($\tau$, код):\\

0000000010111111110110111001111001011011011001101110100010110

0011000000000000100000000001111101000000101110111110010100011

111000110111001001011001011011100110111111110110010110011010\\

0011101011000100100110011111011100011001111001100110111111111

1101011101110011000001111000011001000111101111000100110100000

0000110100010111100101\\

Длина на входе: 368 бит

Длина на выходе: 326 бит (в том числе длина $\tau$ 182 бит, длина кодового слова 144 бита).

\begin{table}
\caption{Результаты вычислений по шагам алгоритма.}
\begin{center}
\begin{longtable}{|l|l|l|l|l|l|}\hline
$i$ & $x_i$ & $p(x_i)$ & $q(x_i)$ & $F$ & $G$ \\\hline
0 & Н & $\frac{1}{46}$ & $\frac{5}{23}$ & $\frac{5}{23}$ & $\frac{1}{46}$\\\hline
1 & е & $\frac{1}{45}$ & $\frac{5}{9}$ & $\frac{95}{414}$ & $\frac{1}{2070}$\\\hline
2 &   & $\frac{9}{44}$ & $\frac{0}{1}$ & $\frac{95}{414}$ & $\frac{1}{10120}$\\\hline
3 & у & $\frac{3}{43}$ & $\frac{39}{43}$ & $\frac{899051}{3916440}$ & $\frac{3}{435160}$\\\hline
4 & з & $\frac{1}{21}$ & $\frac{4}{7}$ & $\frac{1258693}{5483016}$ & $\frac{1}{3046120}$\\\hline
5 & н & $\frac{3}{41}$ & $\frac{29}{41}$ & $\frac{129016163}{562009140}$ & $\frac{3}{124890920}$\\\hline
6 & а & $\frac{3}{20}$ & $\frac{9}{40}$ & $\frac{1474470469}{6422961600}$ & $\frac{9}{2497818400}$\\\hline
7 & в & $\frac{4}{39}$ & $\frac{14}{39}$ & $\frac{3833623241}{16699700160}$ & $\frac{3}{8117909800}$\\\hline
8 & а & $\frac{5}{38}$ & $\frac{9}{38}$ & $\frac{231759950567}{1009572782400}$ & $\frac{3}{61696114480}$\\\hline
9 & й & $\frac{2}{37}$ & $\frac{24}{37}$ & $\frac{94326299893729}{410896122436800}$ & $\frac{3}{1141378117880}$\\\hline
10 &   & $\frac{2}{9}$ & $\frac{0}{1}$ & $\frac{94326299893729}{410896122436800}$ & $\frac{1}{1712067176820}$\\\hline
11 & д & $\frac{3}{35}$ & $\frac{17}{35}$ & $\frac{660284099256919}{2876272857057600}$ & $\frac{1}{19974117062900}$\\\hline
12 & р & $\frac{3}{34}$ & $\frac{13}{17}$ & $\frac{2244965937473899}{9779327713995840}$ & $\frac{3}{679119980138600}$\\\hline
13 & у & $\frac{2}{33}$ & $\frac{10}{11}$ & $\frac{24694625312213321}{107572604853954240}$ & $\frac{1}{3735159890762300}$\\\hline
14 & г & $\frac{1}{16}$ & $\frac{15}{32}$ & $\frac{4489931874947879}{19558655427991680}$ & $\frac{1}{59762558252196800}$\\\hline
15 & а & $\frac{4}{31}$ & $\frac{8}{31}$ & $\frac{7655333846786133839}{33347507504725814400}$ & $\frac{1}{463159826454525200}$\\\hline
16 &   & $\frac{7}{30}$ & $\frac{0}{1}$ & $\frac{7655333846786133839}{33347507504725814400}$ & $\frac{1}{1984970684805108000}$\\\hline
17 & в & $\frac{3}{29}$ & $\frac{10}{29}$ & $\frac{222004681556797881499}{967077717637048617600}$ & $\frac{1}{19188049953116044000}$\\\hline
18 &   & $\frac{3}{14}$ & $\frac{0}{1}$ & $\frac{222004681556797881499}{967077717637048617600}$ & $\frac{3}{268632699343624616000}$\\\hline
19 & т & $\frac{2}{27}$ & $\frac{23}{27}$ & $\frac{52858257513523305121}{230256599437392528000}$ & $\frac{1}{1208847147046310772000}$\\\hline
20 & р & $\frac{1}{13}$ & $\frac{21}{26}$ & $\frac{9162097969010706221}{39911143902481371520}$ & $\frac{1}{15715012911602040036000}$\\\hline
21 & и & $\frac{2}{25}$ & $\frac{3}{5}$ & $\frac{24050507168653103830129}{104766752744013600240000}$ & $\frac{1}{196437661395025500450000}$\\\hline
22 &   & $\frac{5}{24}$ & $\frac{0}{1}$ & $\frac{24050507168653103830129}{104766752744013600240000}$ & $\frac{1}{942900774696122402160000}$\\\hline
23 & д & $\frac{2}{23}$ & $\frac{11}{23}$ & $\frac{2489227491955596246418357}{10843358909005407624840000}$ & $\frac{1}{10843358909005407624840000}$\\\hline
24 & н & $\frac{1}{11}$ & $\frac{15}{22}$ & $\frac{54763004823023117421203869}{238553895998118967746480000}$ & $\frac{1}{119276947999059483873240000}$\\\hline
25 & я & $\frac{1}{21}$ & $\frac{20}{21}$ & $\frac{31081705440094201779602197}{135395454485418873585840000}$ & $\frac{1}{2504815907980249161338040000}$\\\hline
26 & , & $\frac{1}{20}$ & $\frac{1}{5}$ & $\frac{5750115506417427329226406447}{25048159079802491613380400000}$ & $\frac{1}{50096318159604983226760800000}$\\\hline
27 &   & $\frac{4}{19}$ & $\frac{0}{1}$ & $\frac{5750115506417427329226406447}{25048159079802491613380400000}$ & $\frac{1}{237957511258123670327113800000}$\\\hline
28 & у & $\frac{1}{18}$ & $\frac{17}{18}$ & $\frac{1433337830316880573320284989}{6243783094236481145609400000}$ & $\frac{1}{4283235202646226065888048400000}$\\\hline
29 & з & $\frac{1}{17}$ & $\frac{10}{17}$ & $\frac{522362055536108163939411360679}{2275468701405807597503025712500}$ & $\frac{1}{72814998444985843120096822800000}$\\\hline
30 & н & $\frac{1}{16}$ & $\frac{3}{4}$ & $\frac{13372468621724368996848930833383}{58251998755988674496077458240000}$ & $\frac{1}{1165039975119773489921549164800000}$\\\hline
31 & а & $\frac{1}{5}$ & $\frac{1}{5}$ & $\frac{17366842365875803892011598484913}{75651946436348927916983712000000}$ & $\frac{1}{5825199875598867449607745824000000}$\\\hline
32 & в & $\frac{1}{7}$ & $\frac{5}{14}$ & $\frac{6240485356804705531862834388912073}{27184266086128048098169480512000000}$ & $\frac{1}{40776399129192072147254220768000000}$\\\hline
33 & а & $\frac{2}{13}$ & $\frac{3}{13}$ & $\frac{9014034404273463546024094117317439}{39266162124407180586244805184000000}$ & $\frac{1}{265046594339748468957152434992000000}$\\\hline
34 & й & $\frac{1}{12}$ & $\frac{2}{3}$ & $\frac{56164368211242349786765509500208659}{244658394775152432883525324608000000}$ & $\frac{1}{3180559132076981627485829219904000000}$\\\hline
35 &   & $\frac{3}{11}$ & $\frac{0}{1}$ & $\frac{56164368211242349786765509500208659}{244658394775152432883525324608000000}$ & $\frac{1}{11662050150948932634114707139648000000}$\\\hline
36 & в & $\frac{1}{10}$ & $\frac{3}{10}$ & $\frac{80315046542076560195074678585298382379}{349861504528467979023441214189440000000}$ & $\frac{1}{116620501509489326341147071396480000000}$\\\hline
37 &   & $\frac{2}{9}$ & $\frac{0}{1}$ & $\frac{80315046542076560195074678585298382379}{349861504528467979023441214189440000000}$ & $\frac{1}{524792256792701968535161821284160000000}$\\\hline
38 & т & $\frac{1}{8}$ & $\frac{7}{8}$ & $\frac{22999178105355416354633006634615931}{100187043415860058424562571776000000}$ & $\frac{1}{4198338054341615748281294570273280000000}$\\\hline
39 & р & $\frac{1}{7}$ & $\frac{6}{7}$ & $\frac{6746463909534431056386273001165064119891}{29388366380391310237969061991912960000000}$ & $\frac{1}{29388366380391310237969061991912960000000}$\\\hline
40 & и & $\frac{1}{6}$ & $\frac{2}{3}$ & $\frac{809575669144131726766352760139807694387}{3526603965646957228556287439029555200000}$ & $\frac{1}{176330198282347861427814371951477760000000}$\\\hline
41 &   & $\frac{1}{5}$ & $\frac{0}{1}$ & $\frac{809575669144131726766352760139807694387}{3526603965646957228556287439029555200000}$ & $\frac{1}{881650991411739307139071859757388800000000}$\\\hline
42 & г & $\frac{1}{4}$ & $\frac{1}{4}$ & $\frac{269858556381377242255450920046602564795667}{1175534655215652409518762479676518400000000}$ & $\frac{1}{3526603965646957228556287439029555200000000}$\\\hline
43 & о & $\frac{1}{3}$ & $\frac{2}{3}$ & $\frac{485745401486479036059811656083884616632201}{2115962379388174337133772463417733120000000}$ & $\frac{1}{10579811896940871685668862317088665600000000}$\\\hline
44 & д & $\frac{1}{2}$ & $\frac{1}{2}$ & $\frac{285732589109693550623418621225814480371883}{1244683752581279021843395566716313600000000}$ & $\frac{1}{21159623793881743371337724634177331200000000}$\\\hline
45 & а & $\frac{1}{1}$ & $\frac{0}{1}$ & $\frac{285732589109693550623418621225814480371883}{1244683752581279021843395566716313600000000}$ & $\frac{1}{21159623793881743371337724634177331200000000}$\\\hline
\end{longtable}
\end{center}
\end{table}

\newpage
\section*{Реализация арифметического нумерационного кодирования}

\begin{lstlisting}

public class NumericalCoding {
	public static String code(byte[] x) 
		throws UnsupportedEncodingException {
		int[] tau = Utils.tau(x);
		int[] tauBackup = tau.clone();
		
		Fraction F = new Fraction(0, 1);
		Fraction G = new Fraction(1, 1);		
		Fraction[] p = new Fraction[Utils.size];
		Fraction[] q = new Fraction[Utils.size + 1];
		q[0] = new Fraction(0, 1);
		
		for (int i = 0; i < x.length; i++) {
			int n = x.length - i;
			
			for (int j = 1; j <= Utils.size; j++) {
				p[j - 1] = new Fraction(tau[j - 1], n);
				q[j] = q[j - 1].add(p[j - 1]);
			}
			
			int xi = x[i] & 255;
					
			F = F.add(q[xi].multiply(G));
			G = G.multiply(p[xi]);

			tau[xi]--;				
		}
		
		int z = G.inverse().log2up();
		String out = F.nBitsAfterComma(z).toString(2);
		while (out.length() < z) {
			out = "0" + out;
		}
		return Utils.tauIndex(tauBackup) + "|" + out;
	}
	
	public static void main (String[] args) throws IOException {
		String inputFileName = "input.txt";
		BufferedReader in = 
			new BufferedReader(new FileReader(inputFileName));
		String input;
		input = in.readLine();
		in.close();
		String output = code(input.getBytes("cp1251"));
		System.out.println(output);
	}
}	

\end{lstlisting}

\section*{Вычисление последовательности $\tau$ и ее номера}

\begin{lstlisting}
public class Utils {
	public final static int size = 256;
	
	public static int[] tau(byte[] x) {
		int[] tau = new int[size];		
		for (int i = 0; i < x.length; i++) {
			tau[x[i] & 255]++;
		}		
		return tau;
	}
	
	public static String tauIndex(int[] tau) {
		int n = 0;
		for (int i : tau) n += i;
		int m = tau.length;
		BigInteger index = tauIndexImpl(tau, 0, n);
		BigInteger maximum = 
			countTaus(n, m).subtract(BigInteger.ONE);
		StringBuilder rv = new StringBuilder();
		for (int t = index.bitLength(); 
			t < maximum.bitLength(); ++t) {
			rv.append("0");
		}
		if (index.signum() != 0 || 
			rv.length() < maximum.bitLength()) {
			rv.append(index.toString(2));
		}
		return rv.toString();
	}
	
	private static BigInteger 
		tauIndexImpl(int[] tau, int offset, int n) {
		int m = tau.length - offset;
		if (offset == tau.length) {
			return BigInteger.ZERO;
		}
 		BigInteger rv = BigInteger.ZERO;
		for (int t = 0; t < tau[offset]; ++t) {
			rv = rv.add(countTaus(n - t, m - 1));
		}
		return 
		rv.add(tauIndexImpl(tau, offset + 1, n - tau[offset]));
	}
	
	private static BigInteger countTaus(int n, int m) {
		return CNK.c(n + m - 1, m - 1);
	}
}
\end{lstlisting}

\end{document} 